#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct pi {
  int n; int d;
  pi(){};
  pi(int a,int b) {n=a;d=b;}
  void operator= (int i) {
    this->n=i;
  }
};
int s, t;
const int maxn=10000;
vector<bool> isprime(maxn, true);
vector<bool> vis(maxn, false);
void sieve() {
  isprime[0]=isprime[1]=false;
  for(int i=2; i<=maxn; ++i) {
    if(isprime[i])
      for(int j=2*i; j<=maxn; j+=i) isprime[j]=false;
  }
}
void solve() {
  queue<pi> q;
  q.push(pi(s,0));
  while(q.size()) {
    pi cur = q.front();q.pop();
    if(cur.n == t) {cout<<cur.d<<'\n';return;}
    int nxt=cur.n; nxt=nxt/10*10;
    for(int j=0; j<10; ++j) {if(isprime[nxt]&&!vis[nxt])q.push(pi(nxt,cur.d+1)),vis[nxt]=true;nxt+=1;}
    nxt=cur.n/100*100+cur.n%10;
    for(int j=0; j<10; ++j) {if(isprime[nxt]&&!vis[nxt])q.push(pi(nxt,cur.d+1)),vis[nxt]=true;nxt+=10;}
    nxt=cur.n/1000*1000+cur.n%100;
    for(int j=0; j<10; ++j) {if(isprime[nxt]&&!vis[nxt])q.push(pi(nxt,cur.d+1)),vis[nxt]=true;nxt+=100;}
    nxt=cur.n%1000+1000;
    for(int j=0; j<9; ++j) {if(isprime[nxt]&&!vis[nxt])q.push(pi(nxt,cur.d+1)),vis[nxt]=true;nxt+=1000;}
  }
  cout<<"Impossible\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int tc; cin>>tc;
  sieve();
  while(tc--) {
    // cout << "Case #" << t << ": \n"
    fill(vis.begin(), vis.end(), false);
    cin>>s>>t;
    solve();
  }
  return 0;
}
